#ifndef N_CHOOSE_K_SLATES_H
#define N_CHOOSE_K_SLATES_H
/*
 NChooseKSlates.h
 
 Utility code for running multi-seat election on a single-seat method.
 
 This isn't necessarily a good idea, practically speaking.
 The combinatorial explosion can cause the vote data to expand hugely.
 For example, a 6 seat election with 14 choices on the ballot expands every vote into a 3003 choice-long ballot.

 This should probably only be used with VRR and Raw summation, since they don't keep a copy of every vote,
 but it could be used on IRNR if you have enough RAM.
 (IRNR will also get a thousand times* slower, but most computers are fast enough that won't matter.)
 (*or whatever the expansion factor is)
 
 It's not really that bad. Thanks to the magic of the StoredIndexVoteNode and NameIndex,
 each choice is pretty small, an int and a float or about 8 bytes. That 3003 choice-lang ballot

 Due to the fracturing of the vote space, it's probably useless with IRV. No slate would get a meaningful number of first choices.
 */

#include "NamedVotingSystem.h"

#include <assert.h>
#include <limits.h>

/* n choose k = n! / (k! * (n-k)!) */
#ifdef __cplusplus
#define NCKINLINE static inline
#elif 0
#define NCKINLINE
#else
#define NCKINLINE static __inline
#endif

NCKINLINE unsigned long NChooseK(unsigned long n, unsigned long k) {
	// Do internal math in 64 bit, but return 32 bit becasue we assume
	// were hosed if we have to deal with more than four billion permutations.
	unsigned long long nf_kf = n;
	unsigned long long x = n - 1;
	unsigned long long nmkf = n - k;
	unsigned long long nmk = nmkf - 1;
	while ( x > k ) {
		unsigned long long t;
		t = nf_kf * x;
		assert(t > nf_kf);  // watch out for overflow
		nf_kf = t;
		x--;
	}
	// nf_kf == n! / k!
	while ( nmk > 1 ) {
		unsigned long long t;
		t = nmkf * nmk;
		assert(t > nmkf);  // watch out for overflow
		nmkf = t;
		nmk--;
	}
	// nmkf == (n-k)!
	{
		unsigned long long nck = nf_kf / nmkf;
		assert(nck < ULONG_MAX);
		return nck;
	}
}

/*
 Do combinatorial explosion to convert multi-seat election into single seat
 election where everyone is voting on fully elected slates behind the scenes.
 
 Based on ratings votes, a preference for a slate is the sum of the preference for the choices in it.
 
 Silently drops votes passed in with index >= numChoices.
 */
StoredIndexVoteNode* createNChooseKSlateVote( StoredIndexVoteNode* vote, int numChoices, int seats );

/*
 Populate a NameIndex with the names and indecies that match what is generated by createNChooseKSlateVote().
 NameIndex must be empty before using this or createNChooseKSlateVote().
 */
void enumerateNChoseKNameIndex( NameIndex* in, int numChoices, int seats, NameIndex* out );

#endif /* N_CHOOSE_K_SLATES_H */
